package Solution101_200.problem103.zigzagLevelOrder;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/10 18:17
 */
public class Solution {
    /**
     * 双栈
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> leftNodes=new Stack<>();
        leftNodes.add(root);
        Stack<TreeNode> rightNodes=new Stack<>();
        boolean isLeft=true;
        while((isLeft&&leftNodes.size()>0)||(!isLeft&&rightNodes.size()>0)){
            List<Integer> levelResult=new ArrayList<>();
            if(isLeft){
                while (!leftNodes.empty()){
                    TreeNode node=leftNodes.pop();
                    levelResult.add(node.val);
                    if(node.left!=null) {
                        rightNodes.push(node.left);
                    }
                    if(node.right!=null){
                        rightNodes.push(node.right);
                    }
                }
                isLeft=false;
            }else {
                while (!rightNodes.empty()){
                    TreeNode node=rightNodes.pop();
                    levelResult.add(node.val);
                    if(node.right!=null){
                        leftNodes.push(node.right);
                    }
                    if(node.left!=null) {
                        leftNodes.push(node.left);
                    }

                }
                isLeft=true;
            }

            result.add(levelResult);
        }

        return result;
    }

    /**
     * 单栈➕递归，性能更好一点儿
     */

    public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<TreeNode> nodes=new Stack<>();
        nodes.add(root);
        travel(result,nodes,true);
        return result;
    }



    private void travel(List<List<Integer>> result,Stack<TreeNode> nodes,boolean isLeft){
        List<Integer> levelResult=new ArrayList<>();
        Stack<TreeNode> nextLevelNodes=new Stack<>();
        while (!nodes.empty()){
            TreeNode node=nodes.pop();
            levelResult.add(node.val);
            if(isLeft){
                if(node.left!=null) {
                    nextLevelNodes.push(node.left);
                }
                if(node.right!=null){
                    nextLevelNodes.push(node.right);
                }

            }else {
                if(node.right!=null){
                    nextLevelNodes.push(node.right);
                }
                if(node.left!=null){
                    nextLevelNodes.push(node.left);
                }
            }
        }
        result.add(levelResult);
        if(nextLevelNodes.size()==0){
            return;
        }
        travel(result,nextLevelNodes,!isLeft);
    }
}
